package com.note.leetcode;


import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName 对称二叉树
 * @Description TODO
 * @Author QiBin
 * @Date 2020/6/1411:15
 * @Version 1.0
 *
 * //给定一个二叉树，检查它是否是镜像对称的。
 * // 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 * //
 * //     1
 * //   / \
 * //  2   2
 * // / \ / \
 * //3  4 4  3
 * // 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 * //
 * //     1
 * //   / \
 * //  2   2
 * //   \   \
 * //   3    3
 * // 进阶：
 * //
 * // 你可以运用递归和迭代两种方法解决这个问题吗？
 * // Related Topics 树 深度优先搜索 广度优先搜索
 **/
public class 对称二叉树 {
    //递归
    public boolean isSymmetric(Node root) {
        if (root==null)
            return true;
        else {
            return helper(root.getLeft(),root.getRight());
        }
    }

    public boolean helper(Node node1,Node node2){
        if (node1==node2)
            return true;
        if (node1==null||node2==null)
            return false;
        return (node1.getValue()==node2.getValue())
                &&(helper(node1.getLeft(),node2.getRight()))
                &&(helper(node1.getRight(),node2.getLeft()));
    }
    //迭代
    public boolean isSymmetricOtherOne(Node root) {
        return check(root, root);
    }

    public boolean check(Node u, Node v) {
        Queue<Node> q = new LinkedList<Node>();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) {
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) {
                continue;
            }
            if ((u == null || v == null) || (u.getValue() != v.getValue())) {
                return false;
            }

            q.offer(u.getLeft());
            q.offer(v.getRight());

            q.offer(u.getRight());
            q.offer(v.getLeft());
        }
        return true;
    }


}
